package com.lw.leetcode.arr.b;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 787. K 站中转内最便宜的航班
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/24 9:17
 */
public class FindCheapestPrice {


    public static void main(String[] args) {
        FindCheapestPrice test = new FindCheapestPrice();

        // 200
//        int n = 3;
//        int[][] flights = {{0, 1, 100}, {1, 2, 200}, {0, 2, 500}};
//        int src = 0;
//        int dst = 1;
//        int k = 0;


        // -1
//        int n = 5;
//        int[][] flights = {{4,1,1},{1,2,3},{0,3,2},{0,4,10},{3,1,1},{1,4,3}};
//        int src = 0;
//        int dst = 2;
//        int k = 1;


        // 47
//        int n = 17;
//        int[][] flights = {{0,12,28},{5,6,39},{8,6,59},{13,15,7},{13,12,38},{10,12,35},{15,3,23},{7,11,26},{9,4,65},{10,2,38},{4,7,7},{14,15,31},{2,12,44},{8,10,34},{13,6,29},{5,14,89},{11,16,13},{7,3,46},{10,15,19},{12,4,58},{13,16,11},{16,4,76},{2,0,12},{15,0,22},{16,12,13},{7,1,29},{7,14,100},{16,1,14},{9,6,74},{11,1,73},{2,11,60},{10,11,85},{2,5,49},{3,4,17},{4,9,77},{16,3,47},{15,6,78},{14,1,90},{10,5,95},{1,11,30},{11,0,37},{10,4,86},{0,8,57},{6,14,68},{16,8,3},{13,0,65},{2,13,6},{5,13,5},{8,11,31},{6,10,20},{6,2,33},{9,1,3},{14,9,58},{12,3,19},{11,2,74},{12,14,48},{16,11,100},{3,12,38},{12,13,77},{10,9,99},{15,13,98},{15,12,71},{1,4,28},{7,0,83},{3,5,100},{8,9,14},{15,11,57},{3,6,65},{1,3,45},{14,7,74},{2,10,39},{4,8,73},{13,5,77},{10,0,43},{12,9,92},{8,2,26},{1,7,7},{9,12,10},{13,11,64},{8,13,80},{6,12,74},{9,7,35},{0,15,48},{3,7,87},{16,9,42},{5,16,64},{4,5,65},{15,14,70},{12,0,13},{16,14,52},{3,10,80},{14,11,85},{15,2,77},{4,11,19},{2,7,49},{10,7,78},{14,6,84},{13,7,50},{11,6,75},{5,10,46},{13,8,43},{9,10,49},{7,12,64},{0,10,76},{5,9,77},{8,3,28},{11,9,28},{12,16,87},{12,6,24},{9,15,94},{5,7,77},{4,10,18},{7,2,11},{9,5,41}};
//        int src = 13;
//        int dst = 4;
//        int k = 13;

        // 14
//        int n = 10;
//        int[][] flights = {{3, 4, 4}, {2, 5, 6}, {4, 7, 10}, {9, 6, 5}, {7, 4, 4}, {6, 2, 10}, {6, 8, 6}, {7, 9, 4}, {1, 5, 4}, {1, 0, 4}, {9, 7, 3}, {7, 0, 5}, {6, 5, 8}, {1, 7, 6}, {4, 0, 9}, {5, 9, 1}, {8, 7, 3}, {1, 2, 6}, {4, 1, 5}, {5, 2, 4}, {1, 9, 1}, {7, 8, 10}, {0, 4, 2}, {7, 2, 8}};
//        int src = 6;
//        int dst = 0;
//        int k = 7;



        // -1
        int n = 94;
        int[][] flights = test.getArr();
        int src = 17;
        int dst = 33;
        int k = 39;

        long l = System.currentTimeMillis();
        int cheapestPrice = test.findCheapestPrice(n, flights, src, dst, k);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(cheapestPrice);


    }


    private int[][] flights;
    private int[] arr;
    private int[] arr2;
    private Map<Integer, List<Integer>> map;
    private int src;
    private int k;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int length = flights.length;
        for (int i = 0; i < length; i++) {
            int[] flight = flights[i];
            List<Integer> list = map.computeIfAbsent(flight[1], v -> new ArrayList<>());
            list.add(i);
        }
        this.flights = flights;
        this.arr = new int[n];
        this.arr2 = new int[n];
        this.map = map;
        this.src = src;
        this.k = k;
        Arrays.fill(arr, Integer.MAX_VALUE);
        Arrays.fill(arr2, Integer.MAX_VALUE);
        find(dst, 0, 0);
        return arr[src] == Integer.MAX_VALUE ? -1 : arr[src];
    }

    private void find(int t, int count, int sum) {
        if (count > k || map.get(t) == null) {
            return;
        }
        List<Integer> list = map.get(t);
        for (int value : list) {
            int[] flight = flights[value];
            int f = flight[0];
            if (f == src) {
                arr[src] = Math.min(arr[src], sum + flight[2]);
                continue;
            }
            if (arr[src] <= sum + flight[2]) {
                continue;
            }
            if (arr[f] <= sum + flight[2] && arr2[f] <= count) {
                continue;
            }
            arr2[f] = count;
            arr[f] = sum + flight[2];
            find(f, count + 1, arr[f]);
        }
    }

    public int findCheapestPrice2(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int length = flights.length;
        for (int i = 0; i < length; i++) {
            int[] flight = flights[i];
            int a = flight[0];
            List<Integer> list = map.computeIfAbsent(a, v -> new ArrayList<>());
            list.add(i);
        }
        List<Integer> list = map.get(src);
        if (list == null) {
            return -1;
        }
        System.out.println(map);
        int count = 0;
        int min = Integer.MAX_VALUE;
        Stack<Integer> as = new Stack<>();
        Stack<Integer> bs = new Stack<>();
        for (int value : list) {
            int[] flight = flights[value];
            as.add(flight[1]);
            as.add(flight[2]);
        }
        Map<Integer, Integer> m = new HashMap<>(n);
        while (count < k) {
            while (!as.isEmpty()) {
                int p = as.pop();
                int i = as.pop();
                if (i == dst) {
                    min = Math.min(min, p);
                    continue;
                }
                List<Integer> li = map.get(i);
                if (li != null) {
                    for (int value : li) {
                        int[] flight = flights[value];
                        int key = flight[1];
                        m.merge(key, p + flight[2], Math::min);
                        bs.add(key);
                        bs.add(m.get(key));
                    }
                }
            }
            System.out.println(bs.size());
            as = bs;
            bs = new Stack<>();
            count++;
        }
        while (!as.isEmpty()) {
            int p = as.pop();
            int i = as.pop();
            if (i == dst) {
                min = Math.min(min, p);
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }


    private int[][] getArr () {
        String path  = "C:\\lw\\aa.txt";
        String s = readTxtFile(path);

        String[] split = s.split("],\\[");
        int length = split.length;
        int[][] arr = new int[length][3];
        for (int i = 0; i < length; i++) {
            String s1 = split[i];
            String[] split1 = s1.split(",");
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(split1[j]) ;
            }
        }
        return arr;
    }

    public static String readTxtFile(String filePath){
        try {
            String encoding="GBK";
            File file=new File(filePath);
            if(file.isFile() && file.exists()){ //判断文件是否存在
                InputStreamReader read = new InputStreamReader(
                        new FileInputStream(file),encoding);//考虑到编码格式
                BufferedReader bufferedReader = new BufferedReader(read);
                String lineTxt = null;
                StringBuilder sb = new StringBuilder();
                while((lineTxt = bufferedReader.readLine()) != null){
                    sb.append(lineTxt);
                }
                read.close();
                return sb.toString();
            }else{
                System.out.println("找不到指定的文件");
            }
        } catch (Exception e) {
            System.out.println("读取文件内容出错");
            e.printStackTrace();
        }

        return "";
    }


}
